1. Field of the Invention
The present invention relates to the fields of computer systems and computer implemented numerical intensive computing methods. More specifically, the present invention relates to high performance computer systems including parallel processing computers and method steps for solving dense systems of linear equations thereon.
2. Background Information
For some applications, such as determining the radar cross section of aircraft, or simulating flow across an airfoil, very large systems of linear equations are used. These linear equations sometimes range on the order of 250,000 variables or more. It therefore is necessary to manipulate very large matrices comprising 250,000.times.250,000 variables or more. Typical prior art computer implemented methods would have required storage of the entire coefficient matrix, all 250,000.times.250,000 elements, and floating point operations on the order of (8/3).times.(250K).sup.3 to solve one such system of linear equations. Due to the required processing power and I/O speed, problems of these magnitudes are typically reserved for the most powerful supercomputers known in the art. Even employing the most powerful supercomputers known in the art, many of these problems would still require hundreds of hours of computing time to solve.
In U.S. Pat. No. 5,301,342, assigned to the assignee of the present invention, a parallel processing computer and a method implemented thereon was disclosed, allowing these problems to be solved with substantially less storage requirements. Under the disclosed computer implemented method, the coefficient matrix is divided into a plurality of ND row sections, a plurality of ND column sections and ND diagonal sections. Each of these sections is known as a disk section. The disk sections are stored on non-volatile media such as magnetic and/or optical disks, and are brought into memory on an as needed basis. Further, the unknown variables are represented by a vector comprising N sections. Each of the plurality of j row sections and j column sections is factored. Then, the j diagonal section is factored and inverted. These steps are repeated for all values of j that range from 1 to ND. Forward elimination is then performed for all sections in the vector using the coefficient matrix, and finally, back substitution is performed for all sections in the vector using the coefficient matrix. While the disclosed processor and the method implemented thereon substantially addressed the storage requirement dimension of these problems, the floating point operation requirement dimension remains substantially unaddressed.
Thus, it is desirable to have a computer system and method implemented thereon that can solve these dense systems of linear equations with substantially reduced floating point operation requirement as well as storage requirement. Preferably, the reduction would be in multiple orders of magnitude. As will be disclosed in more detail below, the method and apparatus of the present invention achieves these and other desirable results.